from collections import deque
import random
from typing import *
from math import inf


class Solution:

    def countOfSubstrings(self, word: str, k: int) -> int:
        aeiou = "aeiou"  # 元音
        s = dict()  # 元音字典
        for i, v in enumerate(aeiou):
            s[v] = i
        cnt = [0] * 6  # 元音计数，辅音计数
        # 答案，元音种类，全元音左界，辅音足k左界
        ans, type, la, lb = 0, 0, 0, 0
        # dqa 元音坐标， dqb 辅音坐标
        dqa, dqb = deque(), deque()
        # i：窗口右界
        for i, v in enumerate(word):
            p = s.get(v, 5)  # 当前字母种类
            if p < 5:  # 元音
                if cnt[p] == 0:  # 新元音,种类+1
                    type += 1
                dqa.append(i)  # 元音入队
            else:
                dqb.append(i)  # 辅音入队
            cnt[p] += 1  # 某种元音或者辅音计数
            # 检查lb左边界，通过辅音的数量限制lb左边界
            while cnt[5] > k:
                lbv = word[lb]
                lbt = s.get(lbv, 5)
                if lbt < 5:
                    if cnt[lbt] == 1 and dqa[0] == lb:
                        type -= 1
                    if dqa[0] == lb:
                        dqa.popleft()
                        cnt[lbt] -= 1
                else:
                    dqb.popleft()
                    cnt[lbt] -= 1
                lb += 1
            while type == 5 and cnt[s.get(word[dqa[0]])] > 1:
                daqi = dqa.popleft()
                cnt[s.get(word[daqi])] -= 1
            if cnt[5] == k and type == 5:
                ans += min(dqa[0], dqb[0] if k > 0 else inf) - lb + 1
        return ans


s = Solution()
print(s.countOfSubstrings("cuiaeo", 0))
print(s.countOfSubstrings(word="aeioqq", k=1))
print(s.countOfSubstrings(word="aeiou", k=0))
print(s.countOfSubstrings(word="ieaouqqieaouqq", k=1))
print(s.countOfSubstrings(word="iieaouqqieaouqq", k=1))


# arr = ""
# for _ in range(200):
#     arr += chr(random.randint(0, 25) + ord("a"))
# print(arr)
